class BinaryTree{
    public static void main(){
    System.out.println(new BT().Start());
    }
}

class Tree{
    Tree left ;
    Tree right;
    int key ;
    boolean has_left ;
    boolean has_right ;
    Tree my_null ;

    // Initialize a node with a key value and no children
    public boolean Init(int v_key){
    key = v_key ;
    has_left = false ;
    has_right = false ;
    return true ;
    }

    // Update the right child with rn
    public boolean SetRight(Tree rn){
    right = rn ;
    return true ;
    }

    // Update the left child with ln
    public boolean SetLeft(Tree ln){
    left = ln ;
    return true ;
    }

    public Tree GetRight(){
    return right ;
    }

    public Tree GetLeft(){
    return left;
    }

    public int GetKey(){
    return key ;
    }

    public boolean SetKey(int v_key){
    key = v_key ;
    return true ;
    }

    public boolean GetHas_Right(){
    return has_right ;
    }

    public boolean GetHas_Left(){
    return has_left ;
    }

    public boolean SetHas_Left(boolean val){
     has_left = val ;
     return true ;
    }

    public boolean SetHas_Right(boolean val){
     has_right = val ;
     return true ;
    }

    // This method compares two integers and
    // returns true if they are equal and false
    // otherwise
    public boolean Compare(int num1 , int num2){
    boolean ntb ;
    int nti ;

    ntb = false ;
    nti = num2 + 1 ;
    if (num1 < num2) ntb = false ;
    else if (!(num1 < nti)) ntb = false ;
    else ntb = true ;
    return ntb ;
    }


    // Insert a new element in the tree
    public boolean Insert(int v_key){
    Tree new_node ;
    boolean ntb ;
    boolean cont ;
    int key_aux ;
    Tree current_node ;

    new_node = new Tree();
    ntb = new_node.Init(v_key) ;
    current_node = this ;
    cont = true ;
    while (cont){
        key_aux = current_node.GetKey();
        if (v_key < key_aux){
        if (current_node.GetHas_Left())
            current_node = current_node.GetLeft() ;
        else {
            cont = false ;
            ntb = current_node.SetHas_Left(true);
            ntb = current_node.SetLeft(new_node);
        }
        }
        else{
        if (current_node.GetHas_Right())
            current_node = current_node.GetRight() ;
        else {
            cont = false ;
            ntb = current_node.SetHas_Right(true);
            ntb = current_node.SetRight(new_node);
        }
        }
    }
    return true ;
    }


    // Delete an element from the tree
    public boolean Delete(int v_key){
    Tree current_node ;
    Tree parent_node ;
    boolean cont ;
    boolean found ;
    boolean is_root ;
    int key_aux ;
    boolean ntb ;

    current_node = this ;
    parent_node = this ;
    cont = true ;
    found = false ;
    is_root = true ;
    while (cont){
        key_aux = current_node.GetKey();
        if (v_key < key_aux)
        if (current_node.GetHas_Left()){
            parent_node = current_node ;
            current_node = current_node.GetLeft() ;
        }
        else cont = false ;
        else
        if (key_aux < v_key)
            if (current_node.GetHas_Right()){
            parent_node = current_node ;
            current_node = current_node.GetRight() ;
            }
            else cont = false ;
        else {
            if (is_root)
            if ((!current_node.GetHas_Right()) &&
                (!current_node.GetHas_Left()) )
                ntb = true ;
            else
                ntb = this.Remove(parent_node,current_node);
            else ntb = this.Remove(parent_node,current_node);
            found = true ;
            cont = false ;
        }
        is_root = false ;
    }
    return found ;
    }


    // Check if the element to be removed will use the
    // righ or left subtree if one exists
    public boolean Remove(Tree p_node, Tree c_node){
    boolean ntb ;
    int auxkey1 ;
    int auxkey2 ;

    if (c_node.GetHas_Left())
        ntb = this.RemoveLeft(p_node,c_node) ;
    else
        if (c_node.GetHas_Right())
        ntb = this.RemoveRight(p_node,c_node) ;
        else {
        auxkey1 = c_node.GetKey();
        //auxtree01 = p_node.GetLeft() ;
        //auxkey2 = auxtree01.GetKey() ;
        auxkey2 = (p_node.GetLeft()).GetKey() ;
        if (this.Compare(auxkey1,auxkey2)) {
            ntb = p_node.SetLeft(my_null);
            ntb = p_node.SetHas_Left(false);
        }
        else {
            ntb = p_node.SetRight(my_null);
            ntb = p_node.SetHas_Right(false);
        }
        }
    return true ;
    }


    // Copy the child key to the parent until a leaf is
    // found and remove the leaf. This is done with the
    // right subtree
    public boolean RemoveRight(Tree p_node, Tree c_node){
    boolean ntb ;

    while (c_node.GetHas_Right()){
        //auxtree01 = c_node.GetRight() ;
        //auxint02 = auxtree01.GetKey();
        //ntb = c_node.SetKey(auxint02);
        ntb = c_node.SetKey((c_node.GetRight()).GetKey());
        p_node = c_node ;
        c_node = c_node.GetRight() ;
    }
    ntb = p_node.SetRight(my_null);
    ntb = p_node.SetHas_Right(false);
    return true ;
    }


    // Copy the child key to the parent until a leaf is
    // found and remove the leaf. This is done with the
    // left subtree
    public boolean RemoveLeft(Tree p_node, Tree c_node){
    boolean ntb ;

    while (c_node.GetHas_Left()){
        //auxtree01 = c_node.GetLeft() ;
        //auxint02 = auxtree01.GetKey();
        //ntb = c_node.SetKey(auxint02);
        ntb = c_node.SetKey((c_node.GetLeft()).GetKey());
        p_node = c_node ;
        c_node = c_node.GetLeft() ;
    }
    ntb = p_node.SetLeft(my_null);
    ntb = p_node.SetHas_Left(false);
    return true ;
    }

    // Search for an elemnt in the tree
    public int Search(int v_key){
    boolean cont ;
    int ifound ;
    Tree current_node;
    int key_aux ;

    current_node = this ;
    cont = true ;
    ifound = 0 ;
    while (cont){
        key_aux = current_node.GetKey();
        if (v_key < key_aux)
        if (current_node.GetHas_Left())
            current_node = current_node.GetLeft() ;
        else cont = false ;
        else
        if (key_aux < v_key)
            if (current_node.GetHas_Right())
            current_node = current_node.GetRight() ;
            else cont = false ;
        else {
            ifound = 1 ;
            cont = false ;
        }
    }
    return ifound ;
    }

    // Invoke the method to really print the tree elements
    public boolean Print(){
    Tree current_node;
    boolean ntb ;

    current_node = this ;
    ntb = this.RecPrint(current_node);
    return true ;
    }

    // Print the elements of the tree
    public boolean RecPrint(Tree node){
    boolean ntb ;

    if (node.GetHas_Left()){
        //auxtree01 = node.GetLeft() ;
        //ntb = this.RecPrint(auxtree01);
        ntb = this.RecPrint(node.GetLeft());
    } else ntb = true ;
    System.out.println(node.GetKey());
    if (node.GetHas_Right()){
        //auxtree01 = node.GetRight() ;
        //ntb = this.RecPrint(auxtree01);
        ntb = this.RecPrint(node.GetRight());
    } else ntb = true ;
    return true ;
    }

}


// This class invokes the methods to create a tree,
// insert, delete and serach for  elements on it
class BT {

    public int Start(){
    Tree root ;
    boolean ntb ;
    int nti ;

    root = new Tree();
    ntb = root.Init(16);
    ntb = root.Print();
    System.out.println(100000000);
    ntb = root.Insert(8) ;
    ntb = root.Print();
    ntb = root.Insert(24) ;
    ntb = root.Insert(4) ;
    ntb = root.Insert(12) ;
    ntb = root.Insert(20) ;
    ntb = root.Insert(28) ;
    ntb = root.Insert(14) ;
    ntb = root.Print();
    System.out.println(root.Search(24));
    System.out.println(root.Search(12));
    System.out.println(root.Search(16));
    System.out.println(root.Search(50));
    System.out.println(root.Search(12));
    ntb = root.Delete(12);
    ntb = root.Print();
    System.out.println(root.Search(12));

    return 0 ;
    }

}


